Many electronic systems that manipulate images in digital form use techniques to convert images with multiple graylevels into images with two graylevels (bi-level). A simple method to accomplish this conversion is to compare the multi-level input against a fixed threshold value. If the input is greater than the threshold, the output is set to the maximum output level. In the other case, the output is set to the minimum level. In this simple algorithm, the difference between the input level and the output level is ignored.
A current technique known as error diffusion makes use of this ignored difference to create a more accurate bi-level rendition of the input graylevel. This is accomplished by spatially modulating pixels in the output image. The percentage of pixels set to minimum levels in an area of the output image will represent the graylevel of the output image. This technique trades off the spatial resolution of the output system for the graylevel resolution of the input system. One of the original papers discussing error diffusion by Robert Floyd and Louis Steinberg, entitled "4.3: An Adaptive Algorithm for Spatial Grey Scale", Stanford University, Stanford, CA; SID 75 Digest, pp. 36-37, describes the use of this algorithm.
An input pixel with graylevels, is compared against a threshold, and set to either full brightness, or no brightness (on/off). After this decision, an error is calculated between the new level of the pixel and the original level of the pixel. This error is then "diffused" to surrounding pixels before they are compared with a predetermined threshold. The error is diffused to, and summed with an unprocessed pixel, and the pixel is later thresholded, generating yet another error. Thus, any one pixel in the image may be affected by errors of many previous pixels before being processed. Using current error diffusion techniques, this error is calculated by simple linear subtraction of the two levels of the pixel.
Typically, a percentage of the error signal is diffused to each of four pixels that have not been thresholded yet. These might be a pixel adjacent to the pixel being thresholded, and three pixels on the next line of the image. A set of percentages for the error distribution could be referred to as a "error kernel", and typically would add up to 100 percent. An example of such a technique would be as follows:
where P is the pixel being processed, and the ratios define the percentage of error diffused to each of the surrounding pixels. Note that pixels on previous lines receive no portion of the error since they have already been converted to bi-level pixels. At each of the locations receiving the error, it is summed with the pixel, and a range check operation is performed to keep that data within range.
U.S. Pat. No. 4,449,150 in the name of Kato, is directed to a modification of the error diffusion technique. This modification is intended to remove an artifact that is associated with the algorithm. Certain values of inputs will produce noticeable artifacts in the forms of patterns and/or streaks in the output image. Kato solves this by randomizing the threshold used in the original algorithm. Disclosure of the Invention
In accordance with the present invention, the error signal is generated by a look-up table with the advantage that biasing of the signal to reduce truncation artifacts is possible. The generation of these error functions in an empirical task and may require some experimentation.
An electronic imaging system with eight digital bits allocated to represent the graylevel of a pixel would allow a range of 0-255 as valid pixel values. If an input value of 254 is compared to a threshold of 127, the result is an output of 255. In the prior art, this would produce an error of -1. When the error kernel described above is applied, the resulting percentages of error are all less than one. It is not possible to represent these values in an 8-bit digital fixed point number system. Therefore, a truncation error occurs, and error signals that are less than a certain amount are set to zero and do not effect the outcome of the processing.
However, with the use of a look-up table to generate these error signals, the output may be modified from a purely linear response to enable small error signals to still effect the output. Using the same example, an input of 254 would be thesholded to 255, but one error signal could be set to -1 and the other three to 0. In this manner, it would be possible to correct for truncation errors introduced by the fixed point representation used in digital hardware and would eliminate the need for the use of expensive floating point hardware.